public class LCS {
    // 最长公共子序列II
    // https://www.nowcoder.com/practice/6d29638c85bb4ffd80c020fe244baf11?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3DSQL%25E7%25AF%2587%26topicId%3D295
    public String LCS (String s1, String s2) {
        // write code here
        // dp[i][j]表示s1字符串[0,i]之间的字符串和s2字符串[0,j]之间的字符串的最长公共子序列
        s1 = " " + s1;
        s2 = " " + s2;
        String[][] dp = new String[s1.length()][s2.length()];
        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = "";
        }
        for (int j = 1; j < dp[0].length; j++) {
            dp[0][j] = "";
        }
        for (int i = 1; i < s1.length(); i++) {
            for (int j = 1; j < s2.length(); j++) {
                if (s1.charAt(i) == s2.charAt(j)) {
                    dp[i][j] = dp[i - 1][j - 1] + s1.charAt(i);
                } else {
                    dp[i][j] = dp[i - 1][j].length() > dp[i][j - 1].length()
                            ? dp[i - 1][j]
                            : dp[i][j - 1];
                }
            }
        }
        return dp[s1.length() - 1][s2.length() - 1] == "" ? "-1" : dp[s1.length() - 1][s2.length() - 1];
    }

    public static void main(String[] args) {
        String s1 = "1A2C3D4B56";
        String s2 = "B1D23A456A";
        LCS lcs = new LCS();
        System.out.println(lcs.LCS(s1, s2));
    }
}
